The present invention relates to a method and to an apparatus for the determination of a repetitive bit value pattern and, in particular, to a concept for determining repetitive bit value patterns for bits at predetermined positions within a sequence of data words which are generated by program expressions or operations performed on the data words, the program expressions or operations changing or updating the content of a plurality of bits of the data word.
The necessity of deriving a repetitive bit value pattern for particular bits of data words which are caused by operations or high-level programming languages operating on the data words may arise in a wide field of applications. This may, for example, be desirable to store the results of expressions of a high-level programming language, such as, for example, C or C++, in a efficient manner. If, for example, a program loop is evaluated, it might be possible that the second bit of an 8-bit data word is a constant or alters in a repetitive pattern. The bit may change its value repeatedly from 0 to 1. In terms of storage efficiency, it may be appropriate to store the resulting bit sequences of the loop separately for each bit of the data word, such that for the exemplary second bit, the complete result could be stored in an algorithmic manner indicating that the bit sequence “01” shall be repeated a predetermined number of times.
An alternate application may be testing electrical devices, such as, for example, memory devices. The high speed of the presently available electrical equipment or memory may necessitate processing each individual data terminal of the devices independently from the remaining data terminals in order to test with the maximum bandwidth of the device. This is, for example, the case when state of the art memory devices are to be tested, which do comprise a high number of data terminals. When each data terminal is connected to an individual test pin of a memory tester or a test system, each test pin having its own program logic, there exists the necessity of deriving the bit patterns occurring at each individual test pin. With increasing test program complexity, it may be highly desirable to determine a repetitive bit value pattern associated to a predetermined test or data pin, such that the repetitive bit value pattern only has to be stored once, associated by an algorithmic description indicating the number of repetitions necessitated in the course of the program.
Previous approaches to determine the repetitive bit value pattern as, for example, the one described in the IEEE Publication entitled “A True Test Processor Per-Pin Algorithmic Pattern Generator”, Klaus-Dieter Hilliges and Jens Sundermann, 1996, propose to evaluate all expressions of a program first in order to search for a repetitiveness in the resulting bitstream generated by the program. However, this necessitates computing the complete program prior to the extraction of a possibly repeating bit sequence, which is very time and resource consuming.
Moreover, following this approach, there is no constraint regarding the length of a possibly repetitive bit value pattern. Therefore, also the search for a repetitive bit value pattern in the bitstream generated by completely processing the program is extremely time-consuming, since arbitrary bit pattern lengths have to be considered.
Further approaches try to organize the evaluated bitstream within specialized data structures, such as to determine a repetitive bit value pattern by performing certain symmetry operations on those data structures. This approach is, for example, followed by the previously cited document. However, the application of the symmetry operations necessitates plenty of resources, such that a real-time processing is, as well as for the other conventional attempts, not feasible.